package com.aqie.hard.stack;

import java.util.Stack;

/**
 * 84 柱状图中最大的矩形
 */
public class LargestRectangleArea {
    /**
     * 1. 暴力解法 O(n^3)
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minheight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++)
                    minheight = Math.min(minheight, heights[k]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }

    /**
     * 2, O(n^2)
     * @param heights
     * @return
     */
    public int largestRectangleArea2(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minheight = Math.min(minheight, heights[j]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }

    /**
     * 3. 分治
     * todo 用线段树代替遍历来找到区间最小值
     * @param heights
     * @param start
     * @param end
     * @return
     */
    private int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++)
            if (heights[minindex] > heights[i])
                minindex = i;
        return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
    }
    public int largestRectangleArea3(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }

    /**
     * 4. 栈 39ms
     * @param heights
     * @return
     */
    public int largestRectangleArea4(int[] heights) {
        Stack< Integer > stack = new Stack < > ();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; ++i) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);
        }
        while (stack.peek() != -1)
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
    }


    /**
     * 5, 4ms的 就是用数组模拟了一个栈
     * @param heights
     * @return
     */
    public int largestRectangleArea5(int[] heights) {
        if ((heights == null) || (heights.length == 0)) return 0;
        final int N = heights.length;
        int[] s = new int[N + 1];
        int i, top = 0, hi, area = 0;
        s[0] = -1;
        for (i = 0; i < N; i++) {
            hi = heights[i];
            while ((top > 0) && (heights[s[top]] > hi)) {
                area = Math.max(area, heights[s[top]] * (i - s[top - 1] - 1));
                top--;
            }
            s[++top] = i;
        }
        while (top > 0) {
            area = Math.max(area, heights[s[top]] * (N - s[top -1] - 1));
            top--;
        }
        return area;
    }


}
